package com.aliyun.code83.round2.beans.radixtree;


import java.util.LinkedList;

public class RadixTree<T> {
    RadixNode<T> rootNode = null;

    public void addNode(String path, T value) {
        if (this.rootNode == null) {
            this.rootNode = new RadixNode<T>(path, value);
            return;
        }
        addNode(this.rootNode, path, value);
    }

    private boolean addToChild(RadixNode<T> parent, String newPath, T value) {
        char first = newPath.charAt(0);
        boolean foundChild = false;
        for (RadixNode<T> child : parent.children) {
            if (child.path.startsWith(first + "")) {
                foundChild = true;
                addNode(child, newPath, value);
                break;
            }
        }
        return foundChild;
    }

    private void addToParent(RadixNode<T> parent, String path, T value, int matchings) {
        String subpath = parent.path.substring(matchings);
        RadixNode<T> node = new RadixNode<>(subpath, parent.value);
        node.children = parent.children;
        parent.path = path.substring(0, matchings);
        parent.children = new LinkedList<>();
        parent.children.add(node);
        if (matchings < path.length()) {
            parent.value = null;
            String subpath2 = path.substring(matchings);
            RadixNode<T> node2 = new RadixNode<>(subpath2, value);
            parent.children.add(node2);
        } else {
            parent.value = value;
        }
    }

    public void addNode(RadixNode<T> parent, String path, T value) {
        int matchings = 0;
        while (matchings < path.length() && matchings < parent.path.length()) {
            if (path.charAt(matchings) != parent.path.charAt(matchings)) break;
            matchings++;
        }
        if (matchings > 0 && matchings < parent.path.length()) {
            this.addToParent(parent, path, value, matchings);
        } else {
            if (matchings == path.length())
                return;
//                throw new Exception("Dumplicate trail:" + path);
            // 没有匹配或者超过/user -> /usersomething
            String newPath = path.substring(matchings);
            boolean foundInChildren = this.addToChild(parent, newPath, value);
            if (!foundInChildren) {
                RadixNode<T> node = new RadixNode<>(newPath, value);
                parent.children.add(node);
            }
        }
    }

    public T find(String path) {
        T v = find(this.rootNode, path);
        System.out.println("find:" + path + " =>" + v);
        return v;
    }

    private boolean matchPattern(String pattern, String path) {
        if (path.length() < pattern.length())
            return false;
        for (int i = 0; i < pattern.length(); i++) {
            char p = pattern.charAt(i);
            if (p == '*') {
                String arg = path.substring(i);
                System.out.println("arg=" + arg);
                return true;
            }
            if (p == '?') {
                int j = i;
                for (; j < path.length(); j++) {
                    if (path.charAt(j) == '/')
                        break;
                }
                String subpath = path.substring(j);
                String subpattern = pattern.substring(i);
                return matchPattern(subpattern, subpath);
            }
            if (path.charAt(i) != p)
                return false;
        }
        if (path.length() == pattern.length())
            return true;
        return false;

    }

    private T find(RadixNode<T> parent, String path) {
        //System.out.println("->" + path + " in " + parent.path);

        for (int i = 0; i < parent.path.length(); i++) {
            if (path.length() < parent.path.length())
                return null;
            char p = parent.path.charAt(i);
            if (p == '*') {
                String arg = path.substring(i);
                System.out.println("arg=" + arg);
                return parent.value;
            }
            if (p == '?') {
                int j = i;
                for (; j < path.length(); j++) {
                    if (path.charAt(j) == '/')
                        break;
                }
                String arg = path.substring(i, j);
                System.out.println("?arg=" + arg);
                path = path.substring(0, i) + "?" + path.substring(j);
                continue;
            }
            if (path.charAt(i) != p)
                return null;
        }
        if (path.length() == parent.path.length())
            return parent.value;
        // trying to find in children
        String subpath = path.substring(parent.path.length());
        for (RadixNode<T> child : parent.children) {
            char p = child.path.charAt(0);
            if (p == subpath.charAt(0) || p == '*' || p == '?')
                return find(child, subpath);
        }
        return null;
    }

    public void print() {
        printNode("", this.rootNode, 0, 1);
    }

    private void printNode(String prefix, RadixNode<T> node, int index, int total) {
        String a = "└";
        if (total > 1 && index != total - 1) a = "├";
        String line = String.format("%-50s<%s>", prefix + a + node.path, node.value);
//        System.out.println(line);
        int padding = node.path.length();
        if (total > 1 && index != total - 1) {
            prefix += "│";
            padding--;
        }
        for (int i = 0; i < padding; i++)
            prefix += " ";

        int size = node.children.size();
        for (int j = 0; j < size; j++) {
            RadixNode<T> child = node.children.get(j);
            printNode(prefix, child, j, size);
        }
    }
}

